package com.since.data_structure.binarytree;

import com.since.data_structure.binarytree.node.Node;

/**
 * Created by Sincerity on 2020/5/16.
 * 描述：二叉树
 */
class BinaryTree {
    Node root;
    Node pre = null;

    public Node getRoot() {
        return root;
    }

    /**
     * 线索化为二叉树节点
     *
     * @param node
     */
    public void threadedNodes(Node node) {
//如果node==null, 不能线索化
        if (node == null) {
            return;
        }
        //(一)先线索化左子树
        threadedNodes(node.getLeft());
        //(二)线索化当前结点[有难度]
        if (node.getLeft() == null) {
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针的类型,指向前驱结点
            node.setLeftType(1);
        }

        //处理后继结点
        if (pre != null && pre.getRight() == null) {
            //让前驱结点的右指针指向当前结点
            pre.setRight(node);
            //修改前驱结点的右指针类型
            pre.setRightType(1);
        }
        //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;
        //(三)在线索化右子树
        threadedNodes(node.getRight());
    }

    /**
     * 遍历线索化二叉树的方法
     */
    public void threadedBinaryTree() {
        Node node = root;
        while (node != null) {
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }
    }

    /**
     * 设置根节点
     *
     * @param root
     */
    public void setRoot(Node root) {
        this.root = root;
    }

    /**
     * 前序
     */
    public void preOrder() {
        if (root != null) {
            root.preOder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

    /**
     * 中序
     */
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

    /**
     * 后序
     */
    public void postOrder() {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

    public void add(Node node) {
        if (root == null) root = node;
        else root.add(node);
    }

    /**
     * 前序查找
     *
     * @param no
     * @return
     */
    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.prologueSearch(no);
        } else {
            return null;
        }

    }

    /**
     * 中序查找
     *
     * @param no
     * @return
     */
    public Node infixSearch(int no) {
        if (root != null) {
            return root.infixSearch(no);
        } else {
            return null;
        }

    }

    /**
     * 后序查找
     *
     * @param no
     * @return
     */
    public Node postSearch(int no) {
        if (root != null) {
            return root.postSearch(no);
        } else {
            return null;
        }

    }

    public void deleteNode(int no) {
        if (root.value == no) {
            root = null;
        } else {
            root.delete(no);
        }
    }
}
